package personal.learn.algorithm;

import java.util.LinkedList;

/**
 * 深度优先搜索和广度优先搜索
 *
 * @author Chai yansheng
 * @create 2019/8/27
 **/
public class GraphAlgorithm {
    // 图的顶点
    private static class Vertex{
        public int data;
        public Vertex(int data) {
            this.data = data;
        }
    }

    /**
     * 图的邻接表形式
     */
    private static class Graph{
        private int size;
        private Vertex[] vertices;
        private LinkedList<Integer> []adj;
        public Graph(int size) {
            this.size = size;
            // 初始化顶点和邻接矩阵
            vertices = new Vertex[size];
            adj = new LinkedList[size];
            for (int i = 0; i < size; i++) {
                vertices[i] = new Vertex(i);
                adj[i] = new LinkedList<>();
            }
        }
    }

    /**
     * 深度优先遍历
     * @param graph
     * @param start
     * @param visit
     */
    public static void dfs(Graph graph, int start, boolean []visit) {
        System.out.println(graph.vertices[start].data);
        visit[start] = true;
        for (Integer index : graph.adj[start]) {
            if (!visit[index]) {
                dfs(graph, index, visit);
            }
        }
    }
    public static void bfs(Graph graph, int start, boolean []visit, LinkedList<Integer> queue) {
        queue.offer(start);
        while (!queue.isEmpty()) {
            int front = queue.poll();
            if (visit[front]) {
                continue;
            }
            System.out.println(graph.vertices[front].data);
            visit[front] = true;
            for (Integer index : graph.adj[front]) {
                queue.offer(index);
            }
        }
    }
    public static void main(String[] args) {
        Graph graph = new Graph(6);
        graph.adj[0].add(1);
        graph.adj[0].add(2);
        graph.adj[0].add(3);

        graph.adj[1].add(0);
        graph.adj[1].add(3);
        graph.adj[1].add(4);

        graph.adj[2].add(0);

        graph.adj[3].add(0);
        graph.adj[3].add(1);
        graph.adj[3].add(4);
        graph.adj[3].add(5);

        graph.adj[4].add(1);
        graph.adj[4].add(3);
        graph.adj[4].add(5);

        graph.adj[5].add(3);
        graph.adj[5].add(4);
        /**
         * 0 <--> 1
         * 0 <--> 2
         * 0 <--> 3
         * 1 <--> 3
         * 1 <--> 4
         * 3 <--> 4
         * 3 <--> 5
         * 4 <--> 5<
         */
        System.out.println("图的深度优先遍历：");
        dfs(graph, 0, new boolean[graph.size]);
        System.out.println("图的广度优先遍历：");
        bfs(graph, 0, new boolean[graph.size], new LinkedList<Integer>());
    }
}
